package array.double_pointer_AND_sort;
/*      给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

        示例 1：
        输入：nums = [-4,-1,0,3,10]
        输出：[0,1,9,16,100]
        解释：平方后，数组变为 [16,1,0,9,100]
        排序后，数组变为 [0,1,9,16,100]

        示例 2：
        输入：nums = [-7,-3,2,3,11]
        输出：[4,9,9,49,121]*/
public class lc977 {

    public static void main(String[] args) {
        int[] nums=new int[]{-4,-1,0,3,10};
        int[] arr=sortedSquares(nums);
        for (int val:arr
             ) {
            System.out.println(val);
        }

    }
    public static int[] sortedSquares(int[] nums) {
        //双指针法：既然是有序递增，那么越靠近两边的数字的绝对值就越大
        //那么设置两个指针从两边出发分别讲元素存入新建的数组中
        if(nums[0]>=0||nums[nums.length-1]<=0){
            return nums;
        }  //当数组的元素绝对值严格递增的时候，直接返回原数组
        int[] arr=new int[nums.length];
        int high= nums.length-1;
        int low=0;
        int pointer=high;
        while(high>=low){
            if(Math.abs(nums[high])>=Math.abs(nums[low])){
                arr[pointer]=nums[high]*nums[high];
            }else{
                arr[pointer]=nums[low]*nums[low];
            }
            high--;
            low++;
            pointer=pointer-2;
        }


        return arr;
    }
    public int[] sortedSquares2(int[] nums) {  //直接排序法，先都平方，然后排序
        for(int i=0;i<nums.length;++i){
            nums[i]=nums[i]*nums[i];
        }
        for(int i=0;i<nums.length-1;i++)
        {
            for(int j=0;j<nums.length-1-i;j++)
            {
                if(nums[j]>nums[j+1])
                {
                    int temp=nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=temp;
                }
            }
        }
        return nums;
    }
}
